package com.example.system.class21;

/**
 * @Date 2022/8/16
 * @Author Jonathan
 * @Description 最长回文子序列长度
 */
public class Code01_PalindromeSubsequence {
    public static void main(String[] args) {
        String str = "a12b3c43def2ghi1kpm";
        int ret = getLongestPalindromeSubsequenceLength(str);
        System.out.printf("ret is %d\n", ret);
    }

    public static int getLongestPalindromeSubsequenceLength(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        final char[] chars = str.toCharArray();
        return process(chars, 0, chars.length - 1);
    }


    public static int process(char[] chars, int left, int right) {
        if (left == right) {
            return 1;
        }
        if (chars[left] == chars[right]) {
            return process(chars, left + 1, right - 1) + 2;
        } else {
            return Math.max(process(chars, left + 1, right), process(chars, left, right - 1));
        }
    }
}
